COMMENT ⊗   VALID 00014 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	%logic.2[f86,jmc]		Another try at logic for Daedalus
C00003 00003	\input memo.tex[let,jmc]
C00004 00004	\section{Introduction}
C00005 00005
C00006 00006	\section{Why logic in AI}
C00007 00007	\section{History}
C00008 00008	\section{Planning}
C00009 00009	\section{Non-monotonic reasoning}
C00014 00010	\section{Problems}
C00015 00011	\section{Controversies}
C00016 00012	\section{References}
C00017 00013	\centerline{This draft of logic.2[f86,jmc] TEXed on \jmcdate\ at \theTime}
C00018 00014	Outline
C00020 ENDMK
C⊗;
%logic.2[f86,jmc]		Another try at logic for Daedalus

\input memo.tex[let,jmc]
\title{MATHEMATICAL LOGIC AND ARTIFICIAL INTELLIGENCE}
\section{Introduction}
\section{Why logic in AI}
\section{History}
\section{Planning}
\section{Non-monotonic reasoning}

	The requirements of science have often led to new branches
of mathematics.  Computer science is no exception.  In the early
1970s the concept of NP-completeness arose and led to the now
classical $P=NP$ problem --- as sharply posed and apparently as
difficult as any classical mathematical problem.  In the late
1970s, formalized non-monotonic reasoning arose from AI, although
hints can be found earlier, and special cases were treated earlier.

	All previous systems of mathematical logic are monotonic
in the sense that if a conclusion $p$ follows from premisses $A$,
and $B$ is a more inclusive set of premisses, then $p$ follows
from $B$.  In the notation of proof theory: if $A\vdash p$ and
$A ⊂ B$, then $B\vdash p$.
Indeed a proof of $p$ from the premisses $A$ is a sequence of sentences
ending with $p$ each of which is a either a premiss, an axiom or follows
from a subset of the sentences occurring earlier in the proof by one of
the rules of inference.  Therefore, a proof of $p$ from $A$ can also serve as a
proof from $B$.  The semantic notion of entailment is also monotonic; we
say that $A$ entails $p$ (written $A\models p$) if $p$ is true in all
models of $A$.  But if $A\models p$ and $A ⊂ B$, then every model of $B$
is also a model of $A$, which shows that $B\models p$.

	Human common sense reasoning is often non-monotonic in that we
reach a conclusions in the absence of a certain premiss that we would not
reach if the premiss were present.  For example, if I hire you to build a
cage for my bird you will plan to put a roof on it to prevent the bird
from flying away but not if I add that my bird is a penguin.  Of course,
the phenomenon of non-monotonicity was noticed long ago, but it was
swept under the rug in various ways, e.g. by speaking of suppressed
premisses or by invoking probabilities.  However, when AI began to
require computer programs to carry out non-monotonic reasoning, then
it became necessary to formalize it properly.

	Several systems of non-monotonic reasoning have been devised,
and as more common sense reasoning phenomena are investigated, more
systems arise.  I shall mention only the circumscription formalism
of (McCarthy 1980, 1986).  This amounts to putting an
ordering on models of a theory and drawing conclusions that are
true in models minimal in the ordering.  Such inferences are
in general non-monotonic, because when a new premiss is added
to the theory the interpretation that was previously a minimal
model may no longer be a model at all.  Mathematically, such
methods of non-monotonic reasoning come to considering minimization
of logical expressions under constraints.  It is interesting that
such mathematical problems arise from common sense reasoning, because
many of the laws of physics are also conveniently expressed as
minimum principles.
\section{Problems}
\section{Controversies}
\section{References}
\centerline{This draft of logic.2[f86,jmc] TEXed on \jmcdate\ at \theTime}
\centerline{Copyright \copyright\ \number\year\ by John McCarthy}
\vfill\eject\end
Outline
Introduction
\section{Why logic in AI}
\section{History}
\section{Planning}
\section{Non-monotonic reasoning}
\section{Problems}
\section{Controversies}
references